class test_24_08_24 {

    //单向链表 + 哨兵节点实现
    class MyLinkedList {
        int size;
        ListNode Dummy;
        ListNode head;

        class ListNode {
            int val;
            ListNode next;

            public ListNode(int val) {
                this.val = val;
                this.next = null;
            }
        }

        public MyLinkedList() {
            head = null;
            Dummy = new ListNode(0);
            size = 0;
        }

        /**
         * get:获取某个索引的元素
         * index:传入索引
         */
        public int get(int index) {
            if (index < 0 || index >= size) {
                return -1;
            }
            ListNode node = Dummy.next;
            for (int i = 0; i < index; i++) {
                node = node.next;
            }
            return node.val;
        }

        public void addAtHead(int val) {
            ListNode newNode = new ListNode(val);
            ListNode node = Dummy.next;
            newNode.next = Dummy.next; // 更新新节点的 next 指针
            Dummy.next = newNode;      // 更新虚拟头节点的 next 指针
            size++;
        }

        public void addAtTail(int val) {
            ListNode newNode = new ListNode(val);
            ListNode node = Dummy.next;
            while (node.next != null) {
                node = node.next;
            }
            node.next = newNode;
            size++;
        }

        public void addAtIndex(int index, int val) {
            if (index >= size) {
                addAtTail(val);
                return;
            }
            if (index <= 0) {
                addAtHead(val);
                return;
            }
            ListNode newNode = new ListNode(val);
            ListNode prev = Dummy.next;
            for (int i = 0; i < index - 1; i++) {
                prev = prev.next;
            }
            newNode.next = prev.next;
            prev.next = newNode;
            size++;
        }

        public void deleteAtIndex(int index) {
            if (index < 0 || index > size) {
                return;
            } else if (index == 0) {
                Dummy.next = Dummy.next.next;
            } else {
                ListNode prev = Dummy.next;
                for (int i = 0; i < index - 2; i++) {
                    prev = prev.next;
                }
                prev.next = prev.next.next;
            }
            size--;
        }

        public void print() {
            ListNode node = Dummy.next;
            while (node != null) {
                System.out.println(node.val);
                node = node.next;
            }
        }

    }

    //双向链表 + 哨兵节点
    class DoubleLinkedList {
        class Node {
            int date;
            Node next;
            Node prev;

            public Node(int date) {
                this.date = date;
                this.next = null;
                this.prev = null;
            }
        }

        Node head;
        Node tail;
        int size;

        public DoubleLinkedList() {
            this.head = new Node(0);
            this.tail = new Node(0);
            head.next = tail;
            tail.prev = head;
            this.size = 0;
        }

        public void addFirst(int val) {
            Node node = new Node(val);
            Node headnext = head.next;
            node.next = headnext;
            head.prev = node;
            head.next = node;
            node.prev = head;
            size++;
        }

        public void addLast(int val) {
            Node node = new Node(val);
            Node tailprev = tail.prev;
            tailprev.next = node;
            node.prev = tailprev;
            node.next = tail;
            tail.prev = node;
            size++;
        }

        public void insert(int index, int val) {
            if (index < 0)
                return;
            else if (index == 0)
                addFirst(val);
            else if (index >= size)
                addLast(val);
            else {
                Node node = new Node(val);
                Node prev = head.next;
                for (int i = 0; i < index - 1; i++) {
                    prev = prev.next;
                }
                node.next = prev.next;
                prev.prev = node;
                prev.next = node;
                node.prev = prev;
                size++;
            }
        }

        public void removeFirst() {
            head = head.next;
            size--;
        }

        public void removeLast() {
            //Node lastNode = tail.prev;
            if(size == 0)
                return;
            tail.prev.prev.next = tail;
            tail.prev = tail.prev.prev;
            size--;
        }

        public void remove(int index) {
            if (index > size || index < 0)
                return;
            else if (index == 0)
                removeFirst();
            else if (index == size)
                removeLast();
            else {
                Node node = head.next;
                for (int i = 0; i < size - 2; i++) {
                    node = node.next;
                }
                node.next.next.prev = node;
                node.next = node.next.next;

                size--;
            }
        }

        public void printList() {
            Node node = head.next;
            while (node != tail) {
                System.out.println(node.date);
                node = node.next;
            }
        }
    }

    public void main(String[] args) {
        DoubleLinkedList linkedList = new DoubleLinkedList();
        linkedList.addLast(123);
        linkedList.addLast(111);
        linkedList.addLast(1);
        linkedList.removeLast();
        linkedList.addLast(2);
        linkedList.addLast(7);
        linkedList.addFirst(1000);
        linkedList.removeFirst();
        linkedList.remove(3);
        linkedList.remove(2);

        linkedList.printList();
    }

}



